#include<iostream>
#include<vector>
using namespace std;


class Solution {
public:
    bool canJump(vector<int>& nums) {
        vector<bool> rem;
        int len = nums.size();
        rem.resize(len + 10);
        rem[0] = true;
        for (int i = 0; i < len - 1; i++) {
            if (rem[i])
                for (int j = 0; j <= nums[i] && i + j <= len; j++) {
                    rem[i + j] = true;
                }
        }
        return rem[len - 1];
    }
};



class Solution2 {
public:
    bool canJump(vector<int>& nums) {
        int len = nums.size();
        int rightmost = 0;
        for (int i = 0; i < len; i++) {
            if (i <= rightmost) {
                rightmost = max(rightmost, i + nums[i]);
                if (rightmost >= len - 1) {
                    return true;
                }
            }
        }
        return false;
    }
};